package class07;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最大线段重合问题
 * <p>
 * 题目描述
 * 给定很多线段，每条线段都有两个数组 [start, end]，表示线段的开始位置和结束位置，左右都是闭区间。
 * <p>
 * 规定：
 * 线段开始和结束位置一定都是整数值；
 * 线段重合区域的长度必须 >= 1 （比如(1,3) 和 (3,5) 不算重合）
 * 返回线段最多重合区域中，包含了几条线段。
 */
public class Code01_CoverMax {
    public static void main(String[] args) {
        int N = 100;
        int L = 0;
        int R = 200;
        int testTimes = 20000;
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(N, L, R);
            int ans1 = maxCover1(lines);
            int ans2 = maxCover3(lines);
            if (ans1 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end");
    }

    // for test
    public static int[][] generateLines(int N, int L, int R) {
        int size = (int) (Math.random() * N) + 1;
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) {
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }

    // 暴力 O((max-min)*N)
    public static int maxCover1(int[][] lines) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 找到所有区间中开始区间的最小值及最大值
        for (int[] line : lines) {
            min = Math.min(min, line[0]);
            max = Math.max(max, line[1]);
        }
        int coverMax = 0;  // 记录某区间中包含的最大区间数
        for (double p = min + 0.5; p < max; p += 1) {
            // 通过取每个区间中的某个小数值，这里取0.5，来遍历每个区间中，有多少个线段区间在该区间上
            int cur = 0;
            for (int[] line : lines) {
                // 在则+1，否则+0
                cur += (line[0] < p && line[1] > p) ? 1 : 0;
            }
            coverMax = Math.max(coverMax, cur);  // 每次更新在区间上最大区间数
        }
        return coverMax;
    }

    // 大小堆 O(N·log N)
    public static int maxCover2(int[][] l) {
        Line[] lines = new Line[l.length];
        for (int i = 0; i < l.length; ++i) {
            lines[i] = new Line(l[i][0], l[i][1]);
        }
        Arrays.sort(lines, Comparator.comparing(o -> o.start));
        // 小根堆，每一条线段的结尾数值，使用默认的
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int max = 0;
        for (Line line : lines) {
            while (!minHeap.isEmpty() && minHeap.peek() <= line.start) {
                minHeap.poll();
            }
            minHeap.add(line.end);
            max = Math.max(max, minHeap.size());
        }
        return max;
    }

    // 通过封装一个区间对象来方便理解题意
    private static class Line {
        // 左右区间起始
        int start, end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static int maxCover3(int[][] lines) {
        // 对区间进行一个自定义排序，根据start开始的位置排序
        Arrays.sort(lines, Comparator.comparing(o -> o[0]));
        // 小根堆，记录每个区间的终止位置
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;  // 记录某区间中包含的最大区间数
        for (int[] line : lines) {
            // 遍历排序过后的每个区间，检查下个区间的起始位置是否大于等于堆中记录的区间中终止位置
            while (!heap.isEmpty() && heap.peek() <= line[0]) {
                heap.poll();
            }
            heap.add(line[1]);  // 记录遍历到的当前区间的终止位置入堆
            max = Math.max(max, heap.size());
        }
        return max;
    }
}
